21461. Field

Andy is a successful farmer. He has a field sized 1 x N tiles, where each tile can be planted a plant. Andy has 26 kind of plants, which is represented by the letter 'a' - 'z'.

Each month Andy has to pay tax to the government. The government in his place is very picky. He wants the tax in the form of a block of tiles. He also demands that the block must contain at least X_i number of plant type Y_i. A block of tiles is all the tile from range a to b. To minimize the loss, Andy will pay in the smallest block possible. Help Andy to find the length of the smallest block to satisfy the government.

Input. Starts with a number n. The next line is a string of length n containing the letter 'a' to 'z'. The next line is a number k, and for the next k lines are the X_i and Y_i, number and type of plants that must be fulfilled.

Output. Minimum length of block to pay the tax. If Andy can't pay the tax, output "Andy rapopo".

Sample input	Sample output
5 aabac 3 1 a 1 b 1 c	3

РЕШЕНИЕ

скользящее окно

Анализ алгоритма

Поддерживаем скользящее окно [j..i]. Изначально положим i = j = 0. Назовем условием p тот факт, что окно содержит в себе как минимум X_i раз букву Y_i. Если условие p не выполняется, то расширяем окно до [j..i + 1]. Иначе уменьшаем до [j + 1..i]. Среди всех окон, удовлетворяющих условию p, ищем наименьшее.

Реализация алгоритма

#include <stdio.h>

#include <string.h>

#define MAX 100010

int i, j, n, k, a, opt, cond;

char ch, s[MAX];

int x[256], z[256];

int main(void)

{

scanf("%d\n", &n);

gets(s);

scanf("%d",&k);

memset(x,sizeof(x),0);

memset(z,sizeof(z),0);

for (i = 0; i < k; i++)

{

scanf("%d %c",&a,&ch);

x[ch] = a;

}

cond = 0;

i = 0, j = 0;

opt = n + 1;

while (i < n)

{

while (cond < k && j < n)

{

ch = s[j++];

if (++z[ch] == x[ch]) ++cond;

}

if (cond >= k && j - i < opt)

opt = j - i;

ch = s[i++];

if (z[ch]-- == x[ch]) cond--;

}

if (opt > n) printf("Andy rapopo\n");

else printf("%d\n", opt);

}